1110D - Jongmah - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int, int>;
//using ll=long long;

#define loop(x,n) for(int x=0; x<n; x++)
#define loop1(x,n) for(int x=1; x<=n; x++)
#define loopr(x,n) for(int x=n; x-->0;)

#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define mp make_pair
#define all(v) begin(v), end(v)
#define UNTIE_IO ios_base::sync_with_stdio(0);cin.tie(0);

const int MAX=1e6+20;
const int INF=2e9;
const int MOD=998244353;

int dp[MAX][3][3];
int N,M;
int cnt[MAX];

signed main(){
    cin>>N>>M;
    int x;
    loop(i, N){
        cin>>x;
        cnt[x+3]++;
    }

    int ans=0;
    for(int i=4; i<M+6; i++){
        loop(x, 3){
            loop(y, 3){
                dp[i][x][y] = -INF;
                loop(z, 3){
                    if (x>cnt[i]||x+y>cnt[i-1]||x+y+z>cnt[i-2]||y+z>cnt[i-3]||z>cnt[i-4]) continue;
                    dp[i][x][y] = max(dp[i][x][y], dp[i-1][y][z]+x+(cnt[i-2]-x-y-z)/3);
                }
                ans = max(ans, dp[i][x][y]);
            }
        }
    }
    cout << ans << '\n';
}